package Algorithm.Sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Leetcode_1996_游戏中弱角色的数量 {
    class Solution {
        public int numberOfWeakCharacters(int[][] properties) {
            Arrays.sort(properties, (o1, o2) -> {
                return o1[0] == o2[0] ? (o2[1] - o1[1]) : (o1[0] - o2[0]);
            });
            int ans = 0;
            Deque<Integer> st = new ArrayDeque<Integer>();
            for (int[] p : properties) {
                while (!st.isEmpty() && st.peek() < p[1]) {
                    st.pop();
                    ans++;
                }
                st.push(p[1]);
            }
            return ans;
        }
    }

}
